# 77.组合
# 给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。
# 你可以按任何顺序返回答案。
#
# 示例1：
# 输入：n = 4, k = 2
# 输出：
# [
#     [2, 4],
#     [3, 4],
#     [2, 3],
#     [1, 2],
#     [1, 3],
#     [1, 4],
# ]
#
# 示例2：
# 输入：n = 1, k = 1
# 输出：[[1]]
#
# 提示：
# 1 <= n <= 20
# 1 <= k <= n


class Solution:
    def combine(self, n: int, k: int):
        res = []
        path = []
        def backtracking(n, k, index):
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(index,n+1):
                path.append(i)
                backtracking(n, k, i+1)
                path.pop()
        backtracking(n,k,1)
        return res

    def combine(self, n: int, k: int):
        res = []
        path = []
        def backtracking(n, k, index): # 这里index记录的是下一层递归搜索的起始位置
            if len(path) == k:
                res.append(path[:])
                return
            flag_index = n -(k - len(path)) + 1 # 剪枝操作
            for i in range(index,flag_index+1):
                path.append(i) # 处理节点
                backtracking(n, k, i+1)
                path.pop() # 回溯操作
        backtracking(n,k,1)
        return res


if __name__ == '__main__':
    n = 4
    k = 2
    tmp = Solution()
    res =tmp.combine(n,k)
    print(res)